package binarytree;

import java.util.ArrayList;
import java.util.List;

/**
 * 验证是否是合法的二叉搜索树<p>
 * 一个二叉搜索树具有如下特征：<p>
 * &nbsp 1.节点的左子树只包含小于当前节点的数。<p>
 * &nbsp 2.节点的右子树只包含大于当前节点的数。<p>
 * &nbsp 3.所有左子树和右子树自身必须也是二叉搜索树。<p>
 */
public class ValidateBinarySearchTree {

  public static void main(String[] args) {
    TreeNode root = new TreeNode(4);
    root.left = new TreeNode(3);
    root.right = new TreeNode(6);
    root.right.left = new TreeNode(5);
    root.right.right = new TreeNode(7);
  }

  /**
   * 中序遍历二叉搜索树，然后判断中序遍历得到的结果是不是递增的
   */
  class Solution1 {

    public boolean isValidBST(TreeNode root) {
      if (root == null || (root.left == null && root.right == null)) {
        return true;
      }
      List<Integer> list = new ArrayList<>();
      inOrderTraversal(root, list);
      int before = list.get(0);
      for (int i = 1; i < list.size(); ++i) {
        if (list.get(i) > before) {
          before = list.get(i);
        } else {
          return false;
        }
      }
      return true;
    }

    public void inOrderTraversal(TreeNode root, List<Integer> list) {
      if (root == null) {
        return;
      }
      inOrderTraversal(root.left, list);
      list.add(root.val);
      inOrderTraversal(root.right, list);
    }

  }

  /**
   * 使用递归,不要只着眼于当前节点的 leftVal < rootVal < rightVal<p>
   *   要看整个区域
   *
   */
  class Solution2 {

    /**
     * 为什么要用Integer,而不是用int?
     * @param node
     * @param lower
     * @param upper
     * @return
     */
    public boolean isValidBST(TreeNode node, Integer lower, Integer upper) {
      if (node == null) return true;
      int val = node.val;

      if (lower != null && val <= lower) return false;
      if (upper != null && val >= upper) return false;

      boolean leftState = isValidBST(node.left, lower, val);
      boolean rightState = isValidBST(node.right, val, upper);

      return (leftState == true && rightState == true) ? true : false;
    }

    public boolean isValidBST(TreeNode root) {
      return isValidBST(root, null, null);
    }
  }
}
